Harnik có khả năng thi đấu cho đội tuyển Đức hoặc đội tuyển Áo và cuối cùng anh đã quyết định chọn khoác áo đội tuyển Áo dù chưa từng bao giờ sống ở đây. Anh có trận đấu đầu tiên cho tuyển Áo trong trận gao hữu với Cộng hòa Séc và chỉ mất 7 phút có pha lập công đầu tiên, ấn định tỉ số hòa 1-1 của trận đấu.[15]

Harnik có tên trong danh sách 23 cầu thủ Áo tham dự Euro 2008 tổ chức ngay tại Áo.[16] Anh góp mặt trong cả ba trận đấu của đội tuyển Áo tại giải đấu này ở vòng bảng với lần lượt là Croatia, Ba Lan và Đức. Với chỉ 1 điểm/3 trận, Áo bị loại ngay vòng bảng với vị trí thứ ba trong bảng.

Ngày 12 tháng 10 năm 2010, trong khuôn khổ vòng loại Euro 2012, Harnik vào sân từ ghế dự bị đã ghi bàn thắng gỡ hòa 4-4 ở phút 93 trận đấu với Bỉ, giúp Áo giữ được vị trí thứ hai trong bảng.[17] Tuy nhiên sau đó Áo liên tục để thua bốn trận liên tiếp, trong đó có trận thua Đức 6-2, trận đấu mà Harnik ghi được một bàn, đã khiến đội tuyển nước này không còn cơ hội tham dự Euro 2012.[18]

Ngày 8 tháng 9 năm 2015, Harnik lập được cú đúp trong chiến thắng 4-1 trước Thụy Điển tại sân Friends Arena và với trận thắng này đội tuyển Áo đã chính thức lần đầu tiên kể từ năm 2008 vượt qua vòng loại một Giải vô địch bóng đá châu Âu để có mặt ở Pháp vào năm 2016.[19]

Harnik được huấn luyện viên Marcel Koller triệu tập tham dự Euro 2016. Anh được ra sân trong hai trận đấu vòng bảng với Hungary và Bồ Đào Nha. Đội tuyển Áo đã rời giải ngay sau vòng bảng với chỉ vỏn vẹn 1 điểm, đứng cuối bảng F với 1 trận hòa và 2 trận thua, chỉ ghi được 1 bàn thắng và bị thủng lưới 4 bàn.